Automated transaction terminals have been widely used in conjunction with various types of account cards issued to users for purchase or credit transactions. In most systems, the account or credit card allows the user to access a central system maintaining the user's bank account or authorizing a credit transaction through a terminal. A useful development in account cards has been to incorporate a magnetic, semiconductor, or optically written memory for storing account information, current balances, or other user information in the card itself. Such memory cards allow the user to access distributed terminals for off-line transactions, by reading and/or updating the stored information, without needing to have the transaction validated through a central system. A further development is an account card having a memory and its own microprocessor with an internally stored program for securing the data recorded in memory and controlling access to use of the card to an authorized user and/or for authorized transactions.
Account cards having on-board memories can be made secure against data tampering by using a storage medium which is non-erasable, i.e. data is written once on the card and cannot be erased or changed. For example, an EPROM circuit can be permanently written electrically, or an optical record medium can be burned in by laser writing. This requires permanent memory space to be designated on the card, and therefore such memory cards can be used to record data only a limited number of times. In order to extend the number of times or transactions for which a card can be used, it is desirable to store data on the card in a highly compact form.
Account cards having non-erasable memories typically have an initial balance which is permanently written on the card and a transaction memory zone where successive transaction records are stored. If a relatively large initial balance is provided, and the transactions occur as a large number of relatively small purchase amounts, then debiting successive transaction amounts and storing a new balance with each transaction would fill the transaction memory zone rather quickly. Data can therefore be more effectively compacted in such cases by storing the transaction amounts themselves, and using the computing power of a microprocessor for the terminal or incorporated on the card itself to compute the current balance, by subtracting all recorded transaction amounts from the initial balance, with each requested transaction.
Purchase transactions typically span a wide range of values, e.g. from a few cents to hundreds of dollars. The binary records of these values must be able to accomodate the largest allowed amount which is to be recorded in one data record. Thus, an efficient data compaction scheme for account cards with limited memory space would minimize the extent of unused bits in the data records by using shorter binary words for the lesser numerical values. Also, for some types of purchase transactions, there may be certain values which occur frequently. For example, in postage purchase transactions, the most frequently used values might be 22 and 39 cents, for one and two ounce First Class mail, or $4.40 for a book of stamps, or the standard charges for other postal services. For such applications, it would be desirable to replace frequently recurring values with shorter codes.
Data compaction methods can be divided into two approaches: logical compression and physical compression. In logical compression, the most efficient representation is found for the particular type of data to be recorded. In physical compression, patterns or recurrences in the original data are coded or otherwise represented in a more compact form. Physical compression can be divided into two types: reversible compression, also known as noiseless coding or redundancy reduction, can be uncompressed back to the original data; and irreversible compression, also known as fidelity reducing or entropy reduction, is more compact but suffers from some data loss upon uncompression. Where exact numerical records of transactions are to be maintained, physical compression of the reversible type must be used. Data compaction methods which use one or a combination of these approaches are discussed below.
One known data compaction method is variable-field binary storage wherein words of different bit lengths are stored in data fields of different record lengths. Thus, shorter words, i.e. low numerical values, can be stored in a data field of lesser bit length than other fields storing higher numerical values, thereby saving the otherwise unused bits of the shorter words. However, additional bits are required in order to designate the selected data field lengths. Alternatively, a number of different data blocks can be designated to store words in different categories of word lengths. However, where the numbers and lengths of the data are not known beforehand, it is difficult to predict what capacity each block should have in order to accomodate the data efficiently. Inevitably, one block will become full before the others. In either case, the amount of memory space saved is relatively small.
A value encoding method can be used if all values which might possibly be stored are known beforehand and make up a small enough set. Then the data can be represented by shorthand codes indexed to a lookup table of the known set of values. However, this method becomes inefficient if the set of values is large and/or if the elements of the set are changed over time. An alternative method is to dynamically generate a table of values, by starting with an initial table having a limited set of indices, and providing an "escape" index to another table if the first table becomes filled. However, the tables may become filled with seldom used or outdated values, and frequent escapes to other tables may be required. A large number of indices can be coded more efficiently by dividing them into groups of defined word lengths, but this would require knowing the likely values and the groupings of the indices beforehand.
Run length encoding, or recurrence coding, provides for compression of values which are repeated, by coding with a single bit or low number of bits the occurrences repeating serially after the starting value. However, this requires the starting value to be written as a full fixed length word and an escape index to denote the end of the repeating series. If different values repeat interspersedly, rather than serially, the compression obtained by this method is relatively limited. Relative or delta (difference) encoding is used to compress data which are relatively similar in value. However, where the values can vary widely with each occurrence, or where the difference between adjacent values is comparable to the values themselves, only a low compression efficiency is obtained.
Universal or adaptive coding can be used to produce optimum indices for tables used to convert variable length strings of data into fixed length words upon uncompression. However, universal coding depends upon strings of data, rather than serially entered, single values, and requires large character strings to achieve its maximum efficiency.
Statistical encoding uses shorter indices to represent frequently occurring values and longer indices to represent less frequently occurring values. For example, Shannon-Fano coding methods order data values by the number of occurrences, then divide the values into branching subsets, assigning indices with an increasing number of bits as the frequency decreases. Huffman coding methods count the number of occurrences of each value, then treat the numbers as nodes which are summed to the next larger nodes in a branching tree structure, and assign binary bit indices according to the path taken to reach the value. However, statistical encoding methods generally require assessing the frequencies of the values beforehand, e.g., by looking ahead at all of the data to be written prior to compression. They are thus not well suited for transactions where each value is to be compressed and recorded serially with each transaction, where the frequencies of the values are not known beforehand, or where the frequently occurring values may change over time.